package leetcode.code0131;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution2 implements IDebug {

	public List<List<String>> partition(String s) {
		char[] ss = s.toCharArray();
		int len = ss.length;
		boolean[][] dp = new boolean[len][len];
		for (int i = 0; i < len; i++) {
			dp[i][i] = true;
			for (int j = i - 1; j >= 0; j--) {
				if (ss[j] == ss[i] && (j + 1 == i || dp[j + 1][i - 1])) {
					dp[j][i] = true;
				}
			}
		}
		Map<Integer, List<List<String>>> cache = new HashMap<>();
		return this.f(ss, 0, cache, dp);
	}

	private List<List<String>> f(char[] ss, int start, Map<Integer, List<List<String>>> cache, boolean[][] dp) {
		if (cache.containsKey(start)) {
			return cache.get(start);
		}
		if (start == ss.length - 1) {
			List<String> list = new ArrayList<>();
			list.add(new String(ss, start, 1));
			List<List<String>> ans = new ArrayList<>();
			ans.add(list);
			cache.put(start, ans);
			return ans;
		}
		List<List<String>> ans = new ArrayList<>();
		for (int i = start + 1; i <= ss.length; i++) {
			if (dp[start][i - 1]) {
				String cur = new String(ss, start, i - start);
				if (i == ss.length) {
					List<String> list = new ArrayList<>();
					list.add(cur);
					ans.add(list);
				} else {
					List<List<String>> tmp = this.f(ss, i, cache, dp);
					for (List<String> next : tmp) {
						List<String> list = new ArrayList<>();
						list.add(cur);
						list.addAll(next);
						ans.add(list);
					}
				}
			}
		}
		cache.put(start, ans);
		return ans;
	}

	@Override
	public void debug1() {
		List<List<String>> e = HelpDebug.str2intlist2("[[\"a\",\"a\",\"b\"],[\"aa\",\"b\"]]");
		HelpDebug.compare(e, this.partition("aab"));

	}

	@Override
	public void debug2() {
		List<List<String>> e = HelpDebug.str2intlist2("[[\"b\",\"b\"],[\"bb\"]]");
		HelpDebug.compare(e, this.partition("bb"));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
		so.debug2();
		so.debug1();
		so.debug3();
		so.debug4();

	}

}
